/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        46.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 14:32
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列
 */
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        size = nums.size();
        if (size == 0)
            return {};
        vec.reserve(size);
        // 优化，直接把ans元素个数设置为n!个
        int total_size = 1;
        for (int i = 2; i <= size; ++i) {
            total_size *= i;
        }
        ans.reserve(total_size);
        backtrace(nums);
        return ans;
    }

private:
    vector<vector<int>> ans;
    vector<int> vec;
    int size;

    void backtrace( vector<int> &nums) {
        if (size == vec.size()) {
            ans.emplace_back(vec);
            return;
        }
        for (int i = 0; i < size; i++) {
            if (nums[i] == INT_MAX)
                continue;
            vec.push_back(nums[i]);
            int temp = nums[i];
            nums[i] = INT_MAX;
            backtrace(nums);
            vec.pop_back();
            nums[i] = temp;
        }
    }
};